// 95. 不同的二叉搜索树 II
// https://leetcode.cn/problems/unique-binary-search-trees-ii/

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function (n) {
    // 定义dp数组
    // dp[i] 为 1~i的所有搜索二叉树组合 层序遍历

    // 初始化dp
    // dp[0] 为 1~0 啥都没有
    // dp[1] 就1个元素
    // dp[2] 1~2 [1,2] [2,1]
    let dp = [
        [[null]],
        [[1]],
        [
            [1, null, 2],
            [2, 1, null],
        ],
    ];

    for (let i = 3; i <= n; i++) {
        let arr = [];
        // 把j作为根节点，循环从1到i每个数作为根时，左右的组合
        for (let j = 1; j <= i; j++) {
            let left = dp[j - 1];
            let right = JSON.parse(JSON.stringify(dp[i - j]));

            // 修改右字数，右子树的每个数字都大于根节点
            for (let k = 0; k < right.length; k++) {
                for (let l = 0; l < right[k].length; l++) {
                    if (right[k][l] != null) {
                        right[k][l] = right[k][l] + j;
                    }
                }
            }

            // 拼接树，使用层序遍历
            left.forEach((l) => {
                right.forEach((r) => {
                    arr.push(genTreeArray(j, l, r, i));
                });
            });
        }
        dp.push(arr);
    }

    const ret = dp[n].map((v) => genTreeNode(v));

    console.log(JSON.stringify(ret));
    return ret;
};

function genTreeArray(center, left, right, level) {
    let arr = [];
    // 拼接树，使用层序遍历
    arr.push(center);
    let curlevel = 0;
    let startIndex = 0;

    const left_len = left.length;
    const right_len = right.length;

    while (curlevel < level - 1) {
        let count = 2 ** curlevel;
        if (startIndex >= left_len && startIndex >= right_len) break;

        for (let i = 0; i < count; i++) {
            if (startIndex + i >= left_len) {
                arr.push(null);
            } else {
                arr.push(left[startIndex + i]);
            }
        }

        for (let i = 0; i < count; i++) {
            if (startIndex + i >= right_len) {
                arr.push(null);
            } else {
                arr.push(right[startIndex + i]);
            }
        }

        startIndex += count;
        curlevel++;
    }

    return arr;
}

function TreeNode(val, left, right) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
}

function genTreeNode(arr) {
    let arrNode = arr.map((i) => (i ? new TreeNode(i) : null));
    for (let i = 0; i < arrNode.length; i++) {
        const leftIndex = 2 * i + 1;
        const rightIndex = 2 * i + 2;

        if (leftIndex >= arrNode.length) break;

        if (arrNode[i] !== null && arrNode[i].val !== null) {
            arrNode[i].left = arrNode[leftIndex];
            arrNode[i].right = arrNode[rightIndex];
        }
    }

    return arrNode[0];
}

generateTrees(3); // [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
generateTrees(1); // [[1]]
